#include<cstdio>
#include<cstring>
const int mod=10007;
const int maxm=200010;
int dp[maxm],next[maxm];
char p[maxm];

void make_next()
{
	int k=0;
	int m=strlen(p+1);
	next[0]=0;
	for(int i=2;i<=m;i++)
	{
		while(k>0&&p[k+1]!=p[i])
			k=next[k];
		if(p[k+1]==p[i])k++;
		next[i]=k;
	}
}

int Dp(int n)
{
	int ans=0;
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++)
	{
		dp[i]=(dp[next[i]]+1)%mod;
		ans=(ans+dp[i])%mod;
	}
	return ans;
}

int main()
{
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		scanf("%s",p+1);
		make_next();
		printf("%d\n",Dp(n));
	}
	return 0;
}



